package algorithm_demo.demo04.graph;

import java.util.*;

/**
 * https://leetcode.cn/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/
 * @author Api
 * @date 2023/2/20 0:54
 */
public class Solution {
    public static List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        Graph graph = createGraph(edges);
        Set<Edge> set = kruskalMST(graph);
        return null;
    }

    public static void main(String[] args) {
        int[][] arr = new int[][]{{0,1,1},{1,2,1},{2,3,2},{0,3,2},{0,4,3},{3,4,3},{1,4,6}};
        findCriticalAndPseudoCriticalEdges(5, arr);
    }


    public static Set<Edge> kruskalMST(Graph graph) {
        UnionFind unionFind = new UnionFind();
        unionFind.makeSets(graph.nodes.values());
        Set<Edge> ans = new HashSet<>();
        PriorityQueue<Edge> heap = new PriorityQueue<Edge>((o1, o2) -> {
            return o1.weight - o2.weight;
        });
        heap.addAll(graph.edges);
        while (!heap.isEmpty()) {
            Edge edge = heap.poll();
            if (!unionFind.isSameSet(edge.from, edge.to)) {
                unionFind.union(edge.from, edge.to);
                ans.add(edge);
            }
        }
        return ans;
    }

    //优先将二维数组生成图
    public static Graph createGraph(int[][] edges) {
        Graph graph = new Graph();
        for (int[] edge : edges) {
            int weight = edge[2];
            int from = edge[0];
            int to = edge[1];
            //判断图中是否存在该节点
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(weight, fromNode, toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }


    public static class Node {
        public int value;
        public int in;//入度
        public int out;//出度
        public List<Node> nexts;//邻接节点
        public List<Edge> edges;//邻接边


        public Node(int value) {
            this.value = value;
            this.in = 0;
            this.out = 0;
            this.nexts = new ArrayList<>();
            this.edges = new ArrayList<>();
        }
    }

    public static class Edge {
        public int weight;
        public Node from;
        public Node to;

        public Edge(int weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }

    public static class Graph {
        Map<Integer, Node> nodes;
        Set<Edge> edges;

        public Graph() {
            this.nodes = new HashMap<>();
            this.edges = new HashSet<>();
        }
    }

    public static class UnionFind {
        public Map<Node, Node> parents;
        public Map<Node, Integer> size;

        public UnionFind() {
            parents = new HashMap<>();
            size = new HashMap<>();
        }

        public void makeSets(Collection<Node> nodes) {
            parents.clear();
            size.clear();
            for (Node node : nodes) {
                parents.put(node, node);
                size.put(node, 1);
            }
        }

        public boolean isSameSet(Node a, Node b) {
            return findFather(a) == findFather(b);
        }


        public void union(Node a, Node b) {
            if (a == null || b == null) {
                return;
            }
            Node aHead = findFather(a);
            Node bHead = findFather(b);
            if (aHead != bHead) {
                int aSetSize = size.get(aHead);
                int bSetSize = size.get(bHead);
                Node big = aSetSize >= bSetSize ? aHead : bHead;
                Node small = big == aHead ? bHead : aHead;
                parents.put(small, big);
                size.put(big, aSetSize + bSetSize);
                size.remove(small);
            }
        }

        public Node findFather(Node cur) {
            Stack<Node> path = new Stack<>();
            while (cur != parents.get(cur)) {
                path.push(cur);
                cur = parents.get(cur);
            }
            while (!path.isEmpty()) {
                parents.put(path.pop(), cur);
            }
            return cur;
        }
    }
}
